package com.example.myapplication.Algorithm.LinkedListReversal;

public class ReverseList {
    static class ListNode{
        int val;
        ListNode next;

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    ///迭代-反转
    public static ListNode iterate(ListNode head){
        //上一个
        ListNode previous = null;
        //下一个
        ListNode next = null;
        //当前，传入值head
        ListNode current = head;
        //如果当前ListNode，不等于空

        ///current(1,head2)
        ///current(2,head3)
        ///current(3,head4)
        ///current(4,head5)
        ///current(5,null)

        ///因为while,所以才有多次循环
        //////思路：保存当前级指向数据，改变当前级指向，当前级作为上一级，下一级赋值当前级
        while (current!=null){
            ///把head2,保持起来
            next = current.next;///（head2,head3,head4,head5）
            ///把当前的下一个，指向空
            current.next = previous;/// （1,head2）.head2《=(null)   （2,head3）.head3《=(head1)   （3,head4）.head4《=(head2)   （4,head5）.head5《=(head3)   （5,null）.null《=(head4)  返回head5
            ///把当前的ListNode，赋值给对象（上一个）
            previous = current;///（head1,head2,head3,head4,head5）
            ///把next(null)，赋值给当前current
            current = next;///current <=（head2,head3,head4,head5）
        }
        return  previous;
    }

    ///current: node1 node2 node3 node4 node5
    ///

    ///递归-反转
    public static ListNode recursion(ListNode head){
        if(head == null || head.next == null){
            ///(head == null)=>head5  (head.next == null)=>head5
            return head;
        }
        ///因为recursion调用自己,所以才有多次循环
        ListNode new_head = recursion(head.next);///更换，new_head: node2 node3 node4 node5
        head.next.next = head;
        head.next = null;
        ///思路：改变的二级指向，删除第一级指向。采用第二级进行递归


        ///head1.next(2).next(3) =  head1
        ///next(3)<=head1 ----- head1.next(2) = null
        ///head2.next(3).next(4) =  head2
        ///next(4)<=head2 ----- head2.next(3) = null
        ///head3.next(4).next(5) =  head3
        ///next(5)<=head3 ----- head3.next(4) = null
        ///head4.next(5).next(6) =  head4
        ///next(6)<=head4 ----- head4.next(5) = null
        ///head5.next(6).next(7) =  head5
        ///next(7)<=head5 ----- head5.next(6) = null

        return  new_head;
    }

    public static void main(String[] args){
        ListNode node5 = new ListNode(5,null);
        ListNode node4 = new ListNode(4,node5);
        ListNode node3 = new ListNode(3,node4);
        ListNode node2 = new ListNode(2,node3);
        ListNode node1 = new ListNode(1,node2);

        //ListNode previous = iterate(node1);
        ListNode previous = recursion(node1);

        System.out.println(previous);
    }
}
